package info.gridworld.grid;

import java.util.ArrayList;

class SparseGridNode {
    Object occupant;
    int col;
    SparseGridNode next;

    public SparseGridNode(Object occupant, int col, SparseGridNode next) {
        this.occupant = occupant;
        this.col = col;
        this.next = next;
    }
}

public class SparseBoundedGrid1<E> extends AbstractGrid<E> {
    public SparseGridNode[] occArray;
    public int nRows;
    public int nCols;

    public SparseBoundedGrid1(int rows, int cols) {
        if (rows <= 0)
            throw new IllegalArgumentException("rows <= 0");
        if (cols <= 0)
            throw new IllegalArgumentException("cols <= 0");
        this.nCols = cols;
        this.nRows = rows;
        this.occArray = new SparseGridNode[rows];
    }

    @Override
    public int getNumRows() {
        return this.nRows;
    }

    @Override
    public int getNumCols() {
        return this.nCols;
    }

    @Override
    public boolean isValid(Location loc) {
        return 0 <= loc.getRow() && loc.getRow() < getNumRows()
                && 0 <= loc.getCol() && loc.getCol() < getNumCols();
    }

    @Override
    public E put(Location loc, E obj) {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc + " is not valid");
        if (obj == null)
            throw new NullPointerException("obj == null");
        int r = loc.getRow();
        int c = loc.getCol();
        E oldOccupant = this.remove(loc);
        SparseGridNode tmp = occArray[r];
        SparseGridNode newNode = new SparseGridNode(obj, c, tmp);
        occArray[r] = newNode;
        return oldOccupant;

    }

    @Override
    public E remove(Location loc) {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc + " is not valid");
        int r = loc.getRow();
        int c = loc.getCol();

        SparseGridNode prev = null;
        SparseGridNode cur = null;
        for (cur = this.occArray[r]; cur != null; cur = cur.next) {
            if (c == cur.col) {
                if (prev == null && cur == this.occArray[r])
                    occArray[r] = occArray[r].next;
                else {
                    prev.next = cur.next;
                }
            }
            prev = cur;
        }
        if (cur == null)
            return null;
        return (E) cur.occupant;
    }

    @Override
    public E get(Location loc) {
        if (!isValid(loc))
            throw new IllegalArgumentException("Location " + loc + " is not valid");
        int r = loc.getRow();
        int c = loc.getCol();

        for (SparseGridNode cur = this.occArray[r]; cur != null; cur = cur.next) {
            if (c == cur.col) {
                return (E) cur.occupant;
            }
        }
        return null;
    }

    @Override
    public ArrayList<Location> getOccupiedLocations() {
        ArrayList<Location> theLocations = new ArrayList<Location>();

        for (int i = 0; i < this.nRows; ++i) {
            for (SparseGridNode cur = occArray[i]; cur != null; cur = cur.next) {
                Location temp = new Location(i, cur.col);
                theLocations.add(temp);
            }
        }

        return theLocations;
    }
}
